package com.wngbms.algo;

import java.util.HashMap;
import java.util.Map;

import static com.sun.corba.se.impl.util.RepositoryId.cache;

public class _06_LRUBasedArray<T> {

    private static final int DEFAULT_CAPACITY = 1 << 3;
    private int capacity;
    private int count;
    private T[] value;
    private Map<T, Integer> holder;

    public _06_LRUBasedArray() {
        this(DEFAULT_CAPACITY);
    }

    public _06_LRUBasedArray(int capacity) {
        this.capacity = capacity;
        this.value = (T[]) new Object[capacity];
        count = 0;
        holder = new HashMap<>(capacity);
    }

    public void offer(T object) {
        if (object == null) {
            throw new IllegalArgumentException("");
        }
        Integer index = holder.get(object);
        if (index == null) {
            if (ifFull()) {
                removeAndCache(object);
            } else {
                cache(object, count);
            }
        } else {
            update(index);
        }
    }

    private void update(Integer index) {
        T val = value[index];
        rightShift(index);
        holder.put(val, 0);
        value[0] = val;
    }

    private void removeAndCache(T object) {
        int i = --count;
        T val = value[i];
        holder.remove(val);
        cache(object, count);
    }

    private void rightShift(int end) {
        for (int i = end; i > 0; i--) {
            T val = value[i - 1];
            holder.put(val, i);
            value[i] = value[i - 1];
        }
    }

    private void cache(T object, int count) {
        rightShift(count);
        value[0] = object;
        holder.put(object, 0);
        this.count++;
    }

    private boolean ifFull() {
        return capacity == count;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < count; i++) {
            sb.append(value[i]);
            sb.append(" ");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        _06_LRUBasedArray<Integer> lru = new _06_LRUBasedArray<>();
        _06_LRUBasedArray<Integer> lru = new _06_LRUBasedArray<>(4);
        lru.offer(1);
        lru.offer(2);
        lru.offer(3);
        lru.offer(4);
        lru.offer(5);
        System.out.println(lru);
        lru.offer(6);
        lru.offer(7);
        lru.offer(8);
        lru.offer(9);
        System.out.println(lru);
        lru.offer(10);
        System.out.println(lru);
        lru.offer(11);
        System.out.println(lru);
        lru.offer(12);
        System.out.println(lru);

        lru.offer(8);
        System.out.println(lru);
        lru.offer(7);
        System.out.println(lru);
    }
}
